// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包gif实现了gif图像解码器和编码器。wen jian defg
package gif

import (
	"bufio"
	"compress/lzw"
	"errors"
	"fmt"
	"image"
	"image/color"
	"io"
)

var (
	errNotEnough = errors.New("gif: not enough image data")
	errTooMuch   = errors.New("gif: too much image data")
	errBadPixel  = errors.New("gif: invalid pixel value")
)

// 如果io。读卡器也没有ReadByte，那么decode将引入自己的缓冲。
type reader interface {
	io.Reader
	io.ByteReader
}

// 掩码等。
const (
	// 字段。
	fColorTable         = 1 << 7
	fInterlace          = 1 << 6
	fColorTableBitsMask = 7

	// 图形控制标志。
	gcTransparentColorSet = 1 << 0
	gcDisposalMethodMask  = 7 << 2
)

// 处理方法。
const (
	DisposalNone       = 0x01
	DisposalBackground = 0x02
	DisposalPrevious   = 0x03
)

// 区段指示器。
const (
	sExtension       = 0x21
	sImageDescriptor = 0x2C
	sTrailer         = 0x3B
)

// 扩展。
const (
	eText           = 0x01 // 纯文本
	eGraphicControl = 0xF9 // 图形控件
	eComment        = 0xFE // 注释
	eApplication    = 0xFF // 应用程序
)

func readFull(r io.Reader, b []byte) error {
	_, err := io.ReadFull(r, b)
	if err == io.EOF {
		err = io.ErrUnexpectedEOF
	}
	return err
}

func readByte(r io.ByteReader) (byte, error) {
	b, err := r.ReadByte()
	if err == io.EOF {
		err = io.ErrUnexpectedEOF
	}
	return b, err
}

// 解码器是用于解码GIF文件的类型。
type decoder struct {
	r reader

	// 来自页眉。
	vers            string
	width           int
	height          int
	loopCount       int
	delayTime       int
	backgroundIndex byte
	disposalMethod  byte

	// 来自图像描述符。
	imageFields byte

	// 来自图形控制。
	transparentIndex    byte
	hasTransparentIndex bool

	// 已计算。
	globalColorTable color.Palette

	// 解码时使用。
	delay    []int
	disposal []byte
	image    []*image.Paletted
	tmp      [1024]byte // 必须至少为768，这样我们就可以读取颜色表
}

// blockReader解析GIF图像数据的块结构，它包括
// /（n，（n字节））块，1<=n<=255。它是
// LZW解码器的读取器，因此不会受到阻塞的影响。LZW解码器
// 完成后，剩余的0字节块（0，（））将在检查区块读取器是否耗尽时消耗。
// 
// 避免分配bufio。lzw读卡器的读卡器，块读卡器
// 实现io。字节读取器和缓冲区将块放入解码器的“tmp”缓冲区。
type blockReader struct {
	d    *decoder
	i, j uint8 // d.tmp[i:j]包含缓冲字节
	err  error
}

func (b *blockReader) fill() {
	if b.err != nil {
		return
	}
	b.j, b.err = readByte(b.d.r)
	if b.j == 0 && b.err == nil {
		b.err = io.EOF
	}
	if b.err != nil {
		return
	}

	b.i = 0
	b.err = readFull(b.d.r, b.d.tmp[:b.j])
	if b.err != nil {
		b.j = 0
	}
}

func (b *blockReader) ReadByte() (byte, error) {
	if b.i == b.j {
		b.fill()
		if b.err != nil {
			return 0, b.err
		}
	}

	c := b.d.tmp[b.i]
	b.i++
	return c, nil
}

// blockReader必须实现io。读者，但它的读物实际上不应该被称为
// 在实践中。compress/lzw包将只调用ReadByte。
func (b *blockReader) Read(p []byte) (int, error) {
	if len(p) == 0 || b.err != nil {
		return 0, b.err
	}
	if b.i == b.j {
		b.fill()
		if b.err != nil {
			return 0, b.err
		}
	}

	n := copy(p, b.d.tmp[b.i:b.j])
	b.i += uint8(n)
	return n, nil
}

// close主要检测读取一系列数据子块后是否遇到块终止符
// 。它最多允许一个子块的数据。即，如果在LZW数据结束后的一个子块
// 中存在一定数量的字节，则下一个子块必须是块
// 终止符。如果LZW数据的最末端恰好填充了一个子块，则在
// 在块终止符之前最多可能存在一个长度为1的子块。
// 这些设施允许我们支持由不那么严格的编码器创建的GIF。
// 参见https:
func (b *blockReader) close() error {
	if b.err == io.EOF {
		// 读取时遇到干净的块序列终止符。
		return nil
	} else if b.err != nil {
		// 读取时遇到其他错误。
		return b.err
	}

	if b.i == b.j {
		// 我们到达了读取LZW数据的子块的末尾。我们将允许在
		// 中最多有一个子数据块的长度为1字节。
		b.fill()
		if b.err == io.EOF {
			return nil
		} else if b.err != nil {
			return b.err
		} else if b.j > 1 {
			return errTooMuch
		}
	}

	// 子块的一部分仍处于缓冲状态。我们预计下一次尝试
	// 缓冲一个子块将到达块终止符。
	b.fill()
	if b.err == io.EOF {
		return nil
	} else if b.err != nil {
		return b.err
	}

	return errTooMuch
}

// 解码从r读取GIF图像，并将结果存储在d中。
func (d *decoder) decode(r io.Reader, configOnly, keepAllFrames bool) error {
	// 如果r不提供ReadByte，则添加缓冲。
	if rr, ok := r.(reader); ok {
		d.r = rr
	} else {
		d.r = bufio.NewReader(r)
	}

	d.loopCount = -1

	err := d.readHeaderAndScreenDescriptor()
	if err != nil {
		return err
	}
	if configOnly {
		return nil
	}

	for {
		c, err := readByte(d.r)
		if err != nil {
			return fmt.Errorf("gif: reading frames: %v", err)
		}
		switch c {
		case sExtension:
			if err = d.readExtension(); err != nil {
				return err
			}

		case sImageDescriptor:
			if err = d.readImageDescriptor(keepAllFrames); err != nil {
				return err
			}

		case sTrailer:
			if len(d.image) == 0 {
				return fmt.Errorf("gif: missing image data")
			}
			return nil

		default:
			return fmt.Errorf("gif: unknown block type: 0x%.2x", c)
		}
	}
}

func (d *decoder) readHeaderAndScreenDescriptor() error {
	err := readFull(d.r, d.tmp[:13])
	if err != nil {
		return fmt.Errorf("gif: reading header: %v", err)
	}
	d.vers = string(d.tmp[:6])
	if d.vers != "GIF87a" && d.vers != "GIF89a" {
		return fmt.Errorf("gif: can't recognize format %q", d.vers)
	}
	d.width = int(d.tmp[6]) + int(d.tmp[7])<<8
	d.height = int(d.tmp[8]) + int(d.tmp[9])<<8
	if fields := d.tmp[10]; fields&fColorTable != 0 {
		d.backgroundIndex = d.tmp[11]
		// readColorTable会覆盖d.tmp的内容，但这没关系。
		if d.globalColorTable, err = d.readColorTable(fields); err != nil {
			return err
		}
	}
	// d.tmp[12]是像素纵横比，被忽略。
	return nil
}

func (d *decoder) readColorTable(fields byte) (color.Palette, error) {
	n := 1 << (1 + uint(fields&fColorTableBitsMask))
	err := readFull(d.r, d.tmp[:3*n])
	if err != nil {
		return nil, fmt.Errorf("gif: reading color table: %s", err)
	}
	j, p := 0, make(color.Palette, n)
	for i := range p {
		p[i] = color.RGBA{d.tmp[j+0], d.tmp[j+1], d.tmp[j+2], 0xFF}
		j += 3
	}
	return p, nil
}

func (d *decoder) readExtension() error {
	extension, err := readByte(d.r)
	if err != nil {
		return fmt.Errorf("gif: reading extension: %v", err)
	}
	size := 0
	switch extension {
	case eText:
		size = 13
	case eGraphicControl:
		return d.readGraphicControl()
	case eComment:
		// 除了读取数据，别无选择。
	case eApplication:
		b, err := readByte(d.r)
		if err != nil {
			return fmt.Errorf("gif: reading extension: %v", err)
		}
		// 规范要求大小为11，但Adobe有时使用10。
		size = int(b)
	default:
		return fmt.Errorf("gif: unknown extension 0x%.2x", extension)
	}
	if size > 0 {
		if err := readFull(d.r, d.tmp[:size]); err != nil {
			return fmt.Errorf("gif: reading extension: %v", err)
		}
	}

	// 应用程序扩展，以“NETSCAPE2.0”作为字符串，数据中的1表示
	// 此扩展定义循环计数。
	if extension == eApplication && string(d.tmp[:size]) == "NETSCAPE2.0" {
		n, err := d.readBlock()
		if err != nil {
			return fmt.Errorf("gif: reading extension: %v", err)
		}
		if n == 0 {
			return nil
		}
		if n == 3 && d.tmp[0] == 1 {
			d.loopCount = int(d.tmp[1]) | int(d.tmp[2])<<8
		}
	}
	for {
		n, err := d.readBlock()
		if err != nil {
			return fmt.Errorf("gif: reading extension: %v", err)
		}
		if n == 0 {
			return nil
		}
	}
}

func (d *decoder) readGraphicControl() error {
	if err := readFull(d.r, d.tmp[:6]); err != nil {
		return fmt.Errorf("gif: can't read graphic control: %s", err)
	}
	if d.tmp[0] != 4 {
		return fmt.Errorf("gif: invalid graphic control extension block size: %d", d.tmp[0])
	}
	flags := d.tmp[1]
	d.disposalMethod = (flags & gcDisposalMethodMask) >> 2
	d.delayTime = int(d.tmp[2]) | int(d.tmp[3])<<8
	if flags&gcTransparentColorSet != 0 {
		d.transparentIndex = d.tmp[4]
		d.hasTransparentIndex = true
	}
	if d.tmp[5] != 0 {
		return fmt.Errorf("gif: invalid graphic control extension block terminator: %d", d.tmp[5])
	}
	return nil
}

func (d *decoder) readImageDescriptor(keepAllFrames bool) error {
	m, err := d.newImageFromDescriptor()
	if err != nil {
		return err
	}
	useLocalColorTable := d.imageFields&fColorTable != 0
	if useLocalColorTable {
		m.Palette, err = d.readColorTable(d.imageFields)
		if err != nil {
			return err
		}
	} else {
		if d.globalColorTable == nil {
			return errors.New("gif: no color table")
		}
		m.Palette = d.globalColorTable
	}
	if d.hasTransparentIndex {
		if !useLocalColorTable {
			// 克隆全局颜色表。
			m.Palette = append(color.Palette(nil), d.globalColorTable...)
		}
		if ti := int(d.transparentIndex); ti < len(m.Palette) {
			m.Palette[ti] = color.RGBA{}
		} else {
			// 透明索引超出范围，根据规范，这是一个错误
			// 但是Firefox和Google Chrome 
			// 似乎可以，所以我们用
			// 透明颜色放大调色板。见戈朗。org/issue/15059。
			p := make(color.Palette, ti+1)
			copy(p, m.Palette)
			for i := len(m.Palette); i < len(p); i++ {
				p[i] = color.RGBA{}
			}
			m.Palette = p
		}
	}
	litWidth, err := readByte(d.r)
	if err != nil {
		return fmt.Errorf("gif: reading image data: %v", err)
	}
	if litWidth < 2 || litWidth > 8 {
		return fmt.Errorf("gif: pixel size in decode out of range: %d", litWidth)
	}
	// 一个奇妙的魔法。
	br := &blockReader{d: d}
	lzwr := lzw.NewReader(br, lzw.LSB, int(litWidth))
	defer lzwr.Close()
	if err = readFull(lzwr, m.Pix); err != nil {
		if err != io.ErrUnexpectedEOF {
			return fmt.Errorf("gif: reading image data: %v", err)
		}
		return errNotEnough
	}
	// 理论上，lzwr和br都应该耗尽。从中读取
	// 应该会产生（0，io.EOF）。
	// 
	// 规范（附录F-压缩）规定，“
	// 信息代码的结尾……必须是编码器
	// 为图像输出的最后一个代码”。但实际上，giflib（一个广泛使用的C 
	// 库）并不强制执行此操作，因此我们也接受lzwr返回
	// io。ErrUnexpectedEOF（意味着编码流在LZW解码器看到显式结束码之前到达了
	// 的io.EOF），前提是
	// io。上面的ReadFull调用已成功读取len（m.Pix）字节。
	// 参见https:
	if n, err := lzwr.Read(d.tmp[256:257]); n != 0 || (err != io.EOF && err != io.ErrUnexpectedEOF) {
		if err != nil {
			return fmt.Errorf("gif: reading image data: %v", err)
		}
		return errTooMuch
	}

	// 实际上，一些GIF在数据子块
	// 流中有一个额外的字节，我们忽略了这个字节。请参阅https:
	if err := br.close(); err == errTooMuch {
		return errTooMuch
	} else if err != nil {
		return fmt.Errorf("gif: reading image data: %v", err)
	}

	// 检查颜色索引是否在调色板中。
	if len(m.Palette) < 256 {
		for _, pixel := range m.Pix {
			if int(pixel) >= len(m.Palette) {
				return errBadPixel
			}
		}
	}

	// 如有必要，取消隔行扫描。
	if d.imageFields&fInterlace != 0 {
		uninterlace(m)
	}

	if keepAllFrames || len(d.image) == 0 {
		d.image = append(d.image, m)
		d.delay = append(d.delay, d.delayTime)
		d.disposal = append(d.disposal, d.disposalMethod)
	}
	// GIF89a规范第23节（图形控制扩展）规定：
	// “此扩展的范围是第一个图形渲染块
	// 。”因此，我们将GCE字段重置为零。
	d.delayTime = 0
	d.hasTransparentIndex = false
	return nil
}

func (d *decoder) newImageFromDescriptor() (*image.Paletted, error) {
	if err := readFull(d.r, d.tmp[:9]); err != nil {
		return nil, fmt.Errorf("gif: can't read image descriptor: %s", err)
	}
	left := int(d.tmp[0]) + int(d.tmp[1])<<8
	top := int(d.tmp[2]) + int(d.tmp[3])<<8
	width := int(d.tmp[4]) + int(d.tmp[5])<<8
	height := int(d.tmp[6]) + int(d.tmp[7])<<8
	d.imageFields = d.tmp[8]

	// GIF89a规范第20节（图像描述符）规定：“每个图像必须符合
	// 逻辑屏幕描述符中定义的逻辑屏幕边界。”这在概念上与测试类似。Rect（左、上、左+宽、上+高）
	// imageBounds:=图像。Rect（0，0，d.宽度，d.高度）
	// 如果！帧边界。In（imageBounds）{etc}
	// 但是Go图像的语义。矩形类型是r.In（s）为真
	// 每当r为空矩形时，即使r.Min.X>s.Max.X。在这里，我们
	// 想要更严格的东西。
	// 
	// 注意，通过构造，left>=0&&top>=0，所以我们只需要
	// 显式比较帧边界。最大值（左+宽，顶+高）对
	// imageBounds。最大值（d.宽度，d.高度）而非帧边界。Min（左，上）
	// 与imageBounds相对。最小值（0,0）。
	if left+width > d.width || top+height > d.height {
		return nil, errors.New("gif: frame bounds larger than image bounds")
	}
	return image.NewPaletted(image.Rectangle{
		Min: image.Point{left, top},
		Max: image.Point{left + width, top + height},
	}, nil), nil
}

func (d *decoder) readBlock() (int, error) {
	n, err := readByte(d.r)
	if n == 0 || err != nil {
		return 0, err
	}
	if err := readFull(d.r, d.tmp[:n]); err != nil {
		return 0, err
	}
	return int(n), nil
}

// interlaceScan定义了interlace算法的一个过程的顺序。
type interlaceScan struct {
	skip, start int
}

// 交错表示交错GIF图像中的扫描集。
var interlacing = []interlaceScan{
	{8, 0}, // 第1组：每8次。行，从第0行开始。
	{8, 4}, // 第2组：每8次。行，从第4行开始。第三组：每四次。第二排，从第二排开始。
	{2, 1}, // 第4组：每2次。行，从第1行开始。
}

// Unterlace重新排列以m为单位的像素，以考虑隔行扫描输入。
func uninterlace(m *image.Paletted) {
	var nPix []uint8
	dx := m.Bounds().Dx()
	dy := m.Bounds().Dy()
	nPix = make([]uint8, dx*dy)
	offset := 0 // 通过顺序扫描行逐步完成输入。
	for _, pass := range interlacing {
		nOffset := pass.start * dx // 按照pass定义的步骤完成输出。
		for y := pass.start; y < dy; y += pass.skip {
			copy(nPix[nOffset:nOffset+dx], m.Pix[offset:offset+dx])
			offset += dx
			nOffset += dx * pass.skip
		}
	}
	m.Pix = nPix
}

// 解码从r读取GIF图像，并将第一个嵌入的
// 图像作为图像返回。形象
func Decode(r io.Reader) (image.Image, error) {
	var d decoder
	if err := d.decode(r, false, false); err != nil {
		return nil, err
	}
	return d.image[0], nil
}

// GIF表示一个GIF文件中可能存储的多个图像。
type GIF struct {
	Image []*image.Paletted // 连续图像。
	Delay []int             // 连续的延迟时间，每帧一次，以百分之一秒为单位。
	// LoopCount控制动画在显示期间重新启动的次数。
	// LoopCount为0意味着永远循环。
	// LoopCount为-1意味着每个帧只显示一次。
	// 否则，动画循环次数+1次。
	LoopCount int
	// 处理是连续的处理方法，每帧一个。对于
	// 向后兼容性，nil处理可以有效地传递给EncodeAll，
	// 并意味着每个帧的处理方法为0（未指定处理
	// ）。
	Disposal []byte
	// 配置是全局颜色表（调色板）、宽度和高度。零或
	// 空颜色。调色板配置。ColorModel表示每个帧都有自己的
	// 颜色表，没有全局颜色表。每个帧的边界必须在两个点（0,0）和（Config.Width，Config.Height）定义的矩形内。
	// 
	// 为了向后兼容，零值配置可以有效地传递给
	// EncodeAll，这意味着整个GIF的宽度和高度等于
	// 第一帧的边界矩形。马克斯·波因特。
	Config image.Config
	// BackgroundIndex是全局颜色表中的背景索引，用于
	// 与DisposeAckground处理方法一起使用。DecodeAll从r读取GIF图像并返回连续帧DecodeAll
	BackgroundIndex byte
}

func DecodeAll(r io.Reader) (*GIF, error) {
	var d decoder
	if err := d.decode(r, false, true); err != nil {
		return nil, err
	}
	gif := &GIF{
		Image:     d.image,
		LoopCount: d.loopCount,
		Delay:     d.delay,
		Disposal:  d.disposal,
		Config: image.Config{
			ColorModel: d.globalColorTable,
			Width:      d.width,
			Height:     d.height,
		},
		BackgroundIndex: d.backgroundIndex,
	}
	return gif, nil
}

// DecodeConfig返回GIF图像的全局颜色模型和尺寸
// 不解码整个图像。
func DecodeConfig(r io.Reader) (image.Config, error) {
	var d decoder
	if err := d.decode(r, true, false); err != nil {
		return image.Config{}, err
	}
	return image.Config{
		ColorModel: d.globalColorTable,
		Width:      d.width,
		Height:     d.height,
	}, nil
}

func init() {
	image.RegisterFormat("gif", "GIF8?a", Decode, DecodeConfig)
}
